package com.gxc.array;

import java.util.LinkedList;

/**
 *  最大值减去最小值小于或等于num的子数组数量
 *  给定数组arr和整数num， 共返回有多少个子数组满足如下情况：
    max(arr[i..j]) - min(arr[i..j]) <= num
    max(arr[i..j])表示子数组arr[i..j]中的最大值， min(arr[i..j])表示子数组arr[i.中的最小值。

 【要求】
 如果数组长度为N， 请实现时间复杂度为O(N)的解法。
 */
public class LessNumArray {

    public static void main(String[] args) {

    }

    /**
     * 用一个队列记录 i->j 的最大值 qmax
     * 用一个队列记录 i->j 的最小值 qmin
     *
     * qmax-qmin < num j++
     * qmax-qmin > num i++;
     * @param arr
     * @param num
     * @return
     */
    public static int hanlde(int[] arr, int num) {
        if (arr == null || arr.length<2) return 0;
        LinkedList<Integer> qmax = new LinkedList<>();
        LinkedList<Integer> qmin = new LinkedList<>();
        int n = arr.length;
        int left = 0;
        int right = 0;
        int res = 0;
        //拆成  两个循环，解决  arr[qmax.peekFirst()] - arr[qmin.peekFirst()] 《 num  一直小于num,不进入计算的问题
        //while (left<n && right<n) {
        while (left<n) {
            while (right< n ) {
                // >=  等于边界可以更新最大值的right
                while (!qmax.isEmpty() && arr[right]>=arr[qmax.peekLast()]) {
                    qmax.pollLast();
                }
                qmax.push(right);

                // 《=  等于边界可以更新最小值的right
                while (!qmin.isEmpty() && arr[right]<=arr[qmin.peekLast()]) {
                    qmin.pollLast();
                }
                qmin.push(right);

                if (arr[qmax.peekFirst()] - arr[qmin.peekFirst()] > num) {
                    break;
                }
                right++;
            }
            //边界去除
            if (qmax.peekFirst() == left) {
                qmax.pollFirst();
            }
            if (qmin.peekFirst() == left) {
                qmin.pollFirst();
            }
            res = res + right-left;
            left++;
        }
        return res;
    }
}
